This invention relates generally to the field of computer-aided design and graphics. It relates specifically to an apparatus for generating graphics using an arbitrary number of parallel processors, thereby providing very fast graphics processing and displaying features.
The co-pending, co-assigned applications entitled "Sequential Access Memory System", U.S. Ser. No. 07/078,872, now abandoned, and "Memory Address System", U.S. Ser. No. 07/078,873 now abandoned, disclose systems for storing and addressing and accessing pixel data for the pixels of a raster or other display suitable for use with the disclosed invention, and these two applications are hereby incorporated herein by reference.
Interactive 3-D graphics applications now constitute a significant portion of computer-aided design techniques. Using interactive graphic applications an operator manipulates complex models of objects and other graphical representations. Providing realistic rendering of the models and of complex operations upon them, requires a very large amount of arithmetic processing. For example, it is desirable to depict a complex object, such as an automobile; to rotate any image of the object about an axis; to depict shading of object surfaces based on a light source at any location; to cut a section of the object along any plane and display an image of that cross section; and to show a 3-D wire frame image of the object.
Current semi-conductor technology cannot provide the processing power required for these interactive graphics manipulations with a single processor system. Some form of multiprocessor architecture is required.
A typical computer graphics system consists of a computer with peripherals, including disk drives, printers, plotters, etc. and a graphics terminal. A typical graphics terminal consists of a high resolution video display screen, user input devices including a keyboard and mouse and a graphics controller. The graphics controller accepts high level graphics commands generated by the computer, in part in response to user input and generates low level commands to control the display, at the pixel to pixel level.
Dedicated graphics arithmetic processors ("GAPs"), may be used to translate the high level commands to low level commands. Multiple parallel processing GAPs may provide the multi-processing required to achieve the desired speed for interactive use. In order to function properly, an architecture using multiple parallel GAPs must accomplish at least three goals. First, the architecture must process order-dependent commands in the proper order. Second, the architecture must efficiently allocate commands to whichever GAPs are most ready to handle the commands. Finally, the architecture should distribute order dependent commands equally among the GAPs to minimize transmission time of a series of consecutive commands.
Turning to the first goal, it is readily understood that in graphics processing, certain groups of commands must be executed by the graphics controller in a specific order, while other groups of commands may be executed, within limits, according to an arbitrary order. For example, a command to change the color in which the next drawn image will be displayed on the graphics screen must be executed in the proper order; i.e., after completion of the drawing of the previous image and before drawing of the next image. If the command were executed after the next image had been drawn on the screen, it would be impossible to change the color of that image without redrawing the entire image. Thus, the command to change the color must be processed before any commands to draw the image. Similarly, any command which affects the appearance of a pixel on a screen, such as intensity or shade, whether a pixel will show through overlapping pixels, etc., must be executed in its proper order. Transformations from one viewpoint to another provide another example of order dependent commands. The command to change a viewpoint must be processed before processing the commands to calculate the appearance of an object image as seen from the new viewpoint. Generally, a command is order dependent if it is important that either: it be executed after another specific command or that it be executed before another specific command.
Many types of commands are not order dependent. For instance, an image of an object, such as a wire frame drawing, may consist of a large number of vectors. It does not matter which of the many vectors are drawn first, or in what order, so long as after they have all been drawn, the entire image is present in its proper form.
The second and third goals are related. GAP architecture requires satisfaction of the second. A GAP, described more fully below, includes a graphics command input memory, organized on a first-in, first-out ("FIFO") scheme. The GAP input FIFO typically can hold more than one command. However, commands may be rather large. If the system attempts to load a command into a GAP having available in its input FIFO less than the required amount of space, the system will need to reload the command into another GAP or to stall while the GAP reduces the contents in its GAP input FIFO by processing commands already stored there. Thus, it is desirable to provide a mechanism that will evaluate the capacity of each GAP to accept commands, thereby avoiding delays.
The multiprocessor arrangement requires satisfaction of the final goal. If the order dependent commands are not distributed substantially equally among the GAPs, it may be that one GAP will be assigned to process a string of consecutive commands. In that case, it will take longer to transmit the results of the command execution from the GAP to the image memory unit because the GAP must process each one. If a number of GAPs have processed the sequential commands essentially simultaneously, it is only necessary to wait while each GAP transmits the results, rather than waiting while the same GAP processes each command and transmits the results in series.
One known method to accomplish the goal of ordering commands is to require that all GAPs stand idle while order dependent processing takes place and the results of the order dependent processing are sent to image memory. This approach results in low efficiency, because the non-processing GAPs sit idle during times when they need not be.
With respect to the command allocation goals, if all commands delivered to any GAP took the same processing time, a round robin command distribution would function efficiently. By "round robin," it is meant that each GAP is assigned a position in a command receipt cycle, and receives commands in order. Commands would always go to a designated GAP, following the GAP designated as preceding it in the command chain. However, command processing time does vary, depending on the complexity of the command. Thus, in a round robin system, it would be possible that when a GAP's turn to process came around, it would still be processing commands from the preceding cycle and would not be ready to accept additional commands. In that case, all GAPs must wait until the designated GAP becomes ready.
It might also be possible for each GAP to assert an idle signal and a GAP input FIFO half empty signal. The signals might be sent to a central prioritizer. This system could work for two or three GAPs. However, for a greater number of GAPs, the number of required signal lines would become prohibitive.
Thus, several objects of the invention include, to provide an apparatus for multiple GAP processing that maintains the order dependence of commands, distributes commands equally among GAPs and to the GAP most ready to receive them without degrading operation speed.